package day_2022_7_to_8.day48;

/**
 * 颜色分类
 * @author haomin
 * @date 2022/07/17 08:31
 **/
public class Day3_2_Num75_SortColors {
    public static void main(String[] args) {
        int[] arr = {1,2,0};
        sortColors2(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    // 1. 数组原地移动
    public static void sortColors(int[] nums) {
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == 0){
                moveLeft(nums,0,i);
            }
            if(nums[i] == 2){
                moveRight(nums,i,nums.length);
            }
        }
    }
    public static void moveLeft(int[] nums, int start, int end){
        int temp = nums[end];
        for(int i = end;i > start;i--){
            nums[i] = nums[i-1];
        }
        nums[start] = temp;
    }
    public static void moveRight(int[] nums, int start, int end){
        int temp = nums[start];
        for(int i = start;i < end-1;i++){
            nums[i] = nums[i+1];
        }
        nums[end-1] = temp;
    }

    // 2. new个数组
    public static void sortColors2(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        int[] nums2 = new int[nums.length];
        for (int i = 0;i < nums2.length;i++) nums2[i] = 1;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == 0)
                nums2[start++] = 0;
            if(nums[i] == 2)
                nums2[end--] = 2;
        }
        for (int i = 0;i < nums.length;i++)
            nums[i] = nums2[i];
    }

    // 3. 牛逼方法
    public void sortColors3(int[] nums) {
        int num0 = 0, num1 = 0, num2 = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                nums[num2++] = 2;
                nums[num1++] = 1;
                nums[num0++] = 0;
            }else if(nums[i] == 1) {
                nums[num2++] = 2;
                nums[num1++] = 1;
            }else {
                nums[num2++] = 2;
            }
        }
    }

    // 4. 计数排序
    public void sortColors4(int[] nums) {
        int[] count = new int[3];
        for (int i : nums) count[i]++;
        int j = 0;
        for(int i = 0;i < nums.length;i++){
            while (count[i] > 0) nums[j++] = i;
        }
    }
}